#include "./simulated_annealing.h"
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

// Simulated_Annealing algorithm
void Simulated_Annealing::SASolve() {
	// determine the initial temperature
	int tmin = now_tree_.GetVolume(), tmax = now_tree_.GetVolume();
  	transform_times_ = 0;
	for (int i = 1; i <= 10000; i++) {
	vector<int> t;
    t.assign(3, 1);
    Transform(now_tree_, t);
		if (now_tree_.GetVolume() < best_tree_.GetVolume())  best_tree_ = now_tree_;
		tmin = min(tmin, now_tree_.GetVolume());
		tmax = max(tmax, now_tree_.GetVolume());
	}
	temperature_ = (tmax - tmin)  / log(1 / initial_possibility_);

  	int lastans[20];
	vector<int>  cnt;
  	cnt.assign(3, 1);
  	while(temperature_ > stop_eps_) {
		for (int i = 1; i <= random_frequency_; i++) {
      		TTree new_tree = now_tree_;
			int opt = Transform(new_tree, cnt);  // Transform to a new statue randomly
			transform_times_++;

     	 	bool Accept = false;
			int NewVolume = new_tree.GetVolume(), NowVolume = now_tree_.GetVolume();
      		if (NewVolume < NowVolume) Accept = true;  // if the volume of the new solution is smaller then accept it
      		else {
      			double possibility = exp(- (double)(NewVolume - NowVolume) / temperature_);
      			double random = (double)(rand() % 10000) / 10000; 
      			if (random < possibility) Accept = true;  // otherwise accept it with certain possibility
      		}
      	
      		if (Accept) {
          		now_tree_ = new_tree;
       	  		if (opt != -1) cnt[opt]++;
       	  		if (now_tree_.GetVolume() < best_tree_.GetVolume())  best_tree_ = now_tree_; 
      		}
    	}	
    	
	    // if there is no change in solution than break
	    for (int i = 19; i > 0; i--) lastans[i] = lastans[i - 1];
	    lastans[0] = now_tree_.GetVolume();
	    bool change = false;
	    for (int i = 0; i < 19; i++) 
	    	if (lastans[i] != lastans[i + 1]) {
	    		change = true; 
	        break;    	
	      }
	    if (!change) return ;
	    	
	    // drop the temperature 
	    int opt;
	    if (now_tree_.GetVolume() > 2 * original_volume_) opt = 0;
	    else if (now_tree_.GetVolume() > 1.5 * original_volume_) opt = 1;
	    else opt = 2;
	    temperature_ = temperature_ * temperature_drop_velocity_[opt];
  	}
	return;
}

void Simulated_Annealing::GetAns(std::vector<Cube> &cubes) {
	SASolve();
    now_tree_.GetPlacement(cubes);
	return ;
}